package pers.qianyu.month_202101.date_20210122;

/**
 * 547. 省份数量
 * https://leetcode-cn.com/problems/number-of-provinces/
 *
 * @author mizzle rain
 * @date 2021-01-22 23:57
 */
public class FindCircleNum {
    private int[] p;

    private int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        p = new int[n];
        for (int i = 0; i < p.length; i++) p[i] = i;

        int res = n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (isConnected[i][j] == 1 && find(i) != find(j)) {
                    p[find(i)] = find(j);
                    res--;
                }
            }
        }
        return res;
    }
}
